package com.wkh.datastructure.priorityqueue;

import com.wkh.datastructure.queue.Queue;

//优先级队列,基于无序数组实现
public class PriorityQueue <E extends Priority> implements Queue<E> {
    private Priority[] array;
    private int size;

    public PriorityQueue(int capacity) {
        this.array = new Priority[capacity];
    }

    /**
     * 向队列尾插入值
     *
     * @param value 待插入值
     * @return 插入成功返回true，插入失败返回false
     */
    @Override//时间复杂度为O(1)
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        array[size] = value;
        size++;
        return true;
    }

    /**
     * 返回优先级最高的索引
     * @return
     */
    private int selectMax(){
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()){
                max = i;
            }
        }
        return max;
    }
    /**
     * 从队列获取值，并移除
     *
     * @return 如果队列非空返回队头值，否者返回null
     */
    @Override//时间复杂度为O(n)
    public E pool() {
        if (isEmpty()){
            return null;
        }
        int max = selectMax();
        E e = (E)array[max];
        remove(max);
        return e;
    }

    private void remove(int max) {
        if (max<size-1){
            //移动
            System.arraycopy(array,max+1,array,max,size-max-1);
        }
        size--;
        array[size] = null;
    }

    /**
     * 从队头获取值，不移除
     *
     * @return 如果队列非空返回队头值，否则返回null
     */
    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        int max = selectMax();
        E e = (E) array[max];
        return e;
    }

    /**
     * 检查队列是否为空
     *
     * @return 空返回true，否则返回false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查队列是否已满
     *
     * @return 满了返回true，否则返回false
     */
    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
